/*
 * @ProjectName: 编程学习
 * @Copyright:   2018 HangZhou Yiyuery Dev., Ltd. All Right Reserved.
 * @address:     http://xiazhaoyang.tech
 * @date:        2018/9/10 22:02
 * @email:       xiazhaoyang@live.com
 * @description: 本内容仅限于编程技术学习使用，转发请注明出处.
 */
package com.capsule.chapter.algorithm;

import lombok.Data;
import lombok.ToString;

import java.util.*;

/**
 * <p>
 *   已知深渊有N个台阶[1,1000]，每次只能爬2的整数幂（1,2,4...）
 *   列举所有爬出深渊的方式。
 *   INPUT:
 *      共有M行[1,1000]
 *      第一行输入一个数字M表示有多少组测试数据，接着有M-1行，每一行都输入一个N表示深远的台阶数
 *   OUT:
 *      输出可能爬出深渊的方式
 *
 * </p>
 *
 * @author xiazhaoyang
 * @version V1.0
 * @date 2018/9/10 22:02
 * @modificationHistory=========================逻辑或功能性重大变更记录
 * @modify By: {修改人} 2018/9/10
 * @modify reason: {方法名}:{原因}
 * ...
 */
public class StepOutWays {

    private static Map<Integer,List<Step>> stepMap = new HashMap<>(16);

    private static  List<Step> steps = new ArrayList<>();

    //n为总台阶数目
    public static void calculate(Integer n){
        if(null == n || 0 >= n){
            return;
        }
        int j = 0;
        Step step;
        while(sumList(steps) < n){
            step = new Step(2, j++);
            if(sumList(steps) + step.getTotal() > n){
                calculate(n - sumList(steps));
                stepMap.put(n,steps);
                steps = new ArrayList<>();
                break;
            }
            steps.add(step);
        }
    }

    private static int sumList(List<Step> steps) {
        Iterator<Step> iterator = steps.iterator();
        int sum = 0;
        Step next;
        while(iterator.hasNext()){
            next = iterator.next();
            sum += next.getTotal();
        }
        return sum;
    }

    public static void main(String[] args) {
        calculate(10);
        //n-2^0
        //n-2^0-2^1
        //n-2^0-2^1-2^2
        print();

    }

    private static void print() {
        for(Integer m:stepMap.keySet()){
            System.out.println(stepMap.get(m));
            System.out.println(sumList(stepMap.get(m)));//15
        }
    }

    @Data
    @ToString
    static class  Step{

        private int a;
        private int b;

        public Step(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public int getTotal(){
            return Double.valueOf(Math.pow(a,b)).intValue();
        }

    }
}